【聚类算法】谱聚类(Spectral Clustering)

目录：

1、问题描述

2、问题转化

3、划分准则

4、总结

　　谱聚类(Spectral Clustering, SC)是一种基于图论的聚类方法——将带权无向图划分为两个或两个以上的最优子图(sub-Graph)，使子图内部尽量相似，而子图间距离尽量距离较远，以达到常见的聚类的目的。

　　对于图的相关定义如下：

如下图给出一个六个样本所对应的图：此例中对应的损失函数为 w1,5 + w3,4 = 0.3。

　　谱聚类的目的就是找到一个较好的划分准则，将整个样本空间形成的图分成为各个子图(sub-Graph)，一个子图即为一个类别。根据分割子图的准则，可以将其分为不同的谱聚类（Minimum Cut、Ratio Cut and Normalized Cut等）。

　　讲具体算法之前，回顾一些线性代数有关的结论，不清楚的可以查阅相关资料：

　　首先看看这个损失函数，对其进行如下变换：

1、定义qi如下：

当顶点 i 属于子图G1中时，qi = c1。顶点 i 属于子图G2中时，qi = c2。

2、Cut(G1,G2)变形：

当且仅当i，j属于不同子图时，(qi - qj)2/(c1 - c2)2 = 1，否则(qi - qj)2/(c1 - c2)2 = 0。常数1/2：由每个 i 遍历一遍 j ，这样，被剪断的边的权值被计入了两次，所以除以2。

3、Cut(G1,G2)分子变形：

4、拉普拉斯矩阵 L = D - W，满足：

5、问题转化：

由第3步，等式首尾可知：

因此，总结上述推导，有下式：

因为wi,j ≥ 0，所以qTLq对于任意的q ≠ 0，都有 qTLq ≥ 0，所以L为半正定的矩阵，其L为实对称矩阵。有如下三条性质：

第一点在文章开头结论中以提及，不做详述，对于第2点，我们来好好看看这个L。对于文章最初的样本集，有如下矩阵，下图分别对应于W,D,L矩阵。

对于向量λ0=[1,1,1,1,1,1]T总能使得，L*λ0 = 0 = 0*λ0，所以0总是L的特征值，且0特征值对应的特征向量为[1,1,...,1]T。第2点理解了，第3点也自然可以理解了。

　　因此，最终将最小化损失函数Cut(G1,G2)问题转化为最小化多项式qTLq，只不过对应于不同的准则，其限制条件有所不同，可以利用瑞丽熵(Rayleigh quotient)的性质求解，接下来将逐一介绍。

　　首先，来看看型如 qTLq 的多项式的优化问题。在此之前，先看看Rayleigh quotient（具体见维基百科），此处只列出部分性质：

对于Rayleigh quotient定义如下：

利用拉格朗日乘数法，可以求解多项式的 critical points（极值点）问题（具体过程参考Rayleigh quotient：Formulation using Lagrange multipliers）：

我们第二节最后的式子再强调一遍，以便后文阅读，此式记为公式(1)：

　　Minimum Cut 的目标函数即为公式(1)，对于c1，c2取任何数都不影响分类结果（当然不能相等，因为无法区分相等的东西，c1为样本属于G1的标签，同理c2为样本属于G2的标签，标签相等时，就无法区分），但是会影响求解过程：c1，c2 影响瑞丽熵求的求解条件是否满足，即。为了方便求解，我们选择如下，

　　当c1 = - c2 = 1时，即q为：

　　此时最小化公式(1)的求解变为： 

限制条件中，第一条，可以由向量q元素取值只能是1或-1；第二条，上文已提及，e为元素全为1的向量，e为L的最小特征向量，L的所有特征向量正交。

　　此问题求解方法在第3节和3.1之间已经提及，其最优分类方案q为L的最小特征值对应的特征向量，L的最小特征值0（即为目标函数最小值），对应的特征向量即为e。可以解释：可以找到一个使目标函数为0（所剪切边权重之和为0）的方案，为：所有样本属于G1类（因为q此时对应的值全为1，对应i∈G1），0个样本属于G2类。这是始终存在的但毫无意义的分类。因此，将其排出（即第二限制条件的作用）。

　　综上，求解上述问题，只需求解L的第二小的特征值对应的特征向量，对特征向量进行聚类。此时问题的转变：将离散的问题的求解转为连续问题的求解（此处将问题松弛化了，使得NP-hard问题变为了P问题），最后再进行离散化。

　　问题：这样的目标函数忽略的孤立点的存在，如下图：

wh,c